//
// Created by Jason Xu on 2022/11/24.
//
#include <iostream>
using namespace std;
#ifndef SORT_SORTING_H
#define SORT_SORTING_H



template <typename Comparable>
void percDown( vector<Comparable> & a, int i, int n);
template <typename Comparable>
void heapsort( vector<Comparable> &a );
inline int leftChild( int i);
template <typename Comparable>
void merge( vector<Comparable> & a, vector<Comparable> & tmpArray, int leftPos, int rightPos, int rightEnd);
template <typename Comparable>
void mergeSort(vector<Comparable> & a);
template <typename Comparable>
void mergeSort(vector<Comparable> & a, vector<Comparable> & tmpArray, int left, int right);
template<typename Comparable>
void SORT(vector<Comparable> &items);
template <typename Comparable>
void quicksort( vector<Comparable> & a);
template <typename Comparable>
const Comparable & median3 (vector<Comparable> & a, int left, int right);
template <typename Comparable>
void quicksort( vector<Comparable> &a, int left, int right);
template<typename Comparable>
void insertionSort(vector<Comparable> &a, int left, int right);



///堆排序----------------7.10
template <typename Comparable>
void heapsort( vector<Comparable> &a )
{
    for ( int i = a.size( ) / 2 - 1; i >= 0; --i )
        percDown( a, i, a.size());
    for ( int j = a.size() - 1; j > 0; --j ){
        std::swap( a[0], a[j]);
        percDown(a, 0, j);
    }
}

inline int leftChild( int i){
    return 2 * i + 1;
}

template <typename Comparable>
void percDown( vector<Comparable> & a, int i, int n){
    int child;
    Comparable tmp;

    for( tmp = std::move( a[i]);leftChild(i)<n;i = child){
        child = leftChild(i);
        if( child != n-1 && a[child]<a[child+1])
            ++child;
        if( tmp<a[child])
            a[i]=std::move(a[child]);
        else break;
    }
    a[i] = std::move(tmp);
}

///归并排序---------------------
///7.11

template <typename Comparable>
void mergeSort(vector<Comparable> & a)
{
    vector<Comparable> tmpArray(a.size());
    mergeSort(a, tmpArray, 0, a.size()-1);
}

template <typename Comparable>
void mergeSort(vector<Comparable> & a, vector<Comparable> & tmpArray, int left, int right)
{
    if (left < right){
        int center = (left + right) /2;
        mergeSort(a, tmpArray, left, center);
        mergeSort(a,tmpArray, center+1, right);
        merge(a, tmpArray, left, center+1, right);
    }
}

///7.12

template <typename Comparable>
void merge( vector<Comparable> & a, vector<Comparable> & tmpArray, int leftPos, int rightPos, int rightEnd)
{
    int leftEnd = rightPos -1;
    int tmpPos = leftPos;
    int numElements = rightEnd - leftPos + 1;

    ///主循环

    while(leftPos <= leftEnd && rightPos <=rightEnd)
        if( a[leftPos] <= a[rightPos])
            tmpArray[tmpPos++] = std::move(a[leftPos++]);
        else
            tmpArray[tmpPos++] = std::move(a[rightPos++]);
    while(rightPos <= rightEnd)
        tmpArray[tmpPos++] = std::move(a[rightPos++]);

    for( int i=0; i<numElements; ++i, --rightEnd)
        a[rightEnd] = std::move(tmpArray[rightEnd]);
}


///7.13 递归排序
template<typename Comparable>
void SORT(vector<Comparable> &items)
{
    if (items.size()>1)
    {
        vector<Comparable> smaller;
        vector<Comparable> same;
        vector<Comparable> larger;

        auto chosenItem = items[ items.size()/2];

        for(auto & i :items){
            if(i<chosenItem)
                smaller.push_back(std::move(i));
            else if(chosenItem<i)
                larger.push_back(std::move(i));
            else same.push_back(std::move(i));
        }

    SORT(smaller);
    SORT(larger);

    std::move(begin(smaller),end(smaller),begin(items));
    std::move(begin(same),end(same),begin(items)+smaller.size());
    std::move(begin(larger),end(larger),end(items)=larger.size());
    }
}


///7.15 快速驱动

template <typename Comparable>
void quicksort( vector<Comparable> & a)
{
    quicksort(a ,0 , a.size()-1);
}


///7.16 分隔代码
template <typename Comparable>
const Comparable & median3 (vector<Comparable> & a, int left, int right)
{
    int center = (left + right )/2;
    if( a[center]<a[left])
        std::swap(a[left],a[center]);
    if(a[right]<a[left])
        std::swap(a[left],a[right]);
    if(a[right]<a[center])
        std::swap(a[center],a[right]);
    std::swap(a[center],a[right-1]);
    return a[right-1];
}

///7.17 快速排序的主例程
template <typename Comparable>
void quicksort( vector<Comparable> &a, int left, int right)
{
    if (left+10 <= right)
    {
        const Comparable & pivot= median3(a, left, right);
            ///开始分割
        int i = left, j = right -1;
        for(;;){
            while(a[++i]<pivot){}
            while(pivot<a[--j]){}
            if(i<j)
                std::swap(a[i],a[j]);
            else break;
        }
        std::swap(a[i],a[right-1]);
        quicksort(a,left,i-1);
        quicksort(a,i+1,right);
    }
    else insertionSort(a,left,right); //对子数组进行一次插入排序
}

///-----写一个插入排序
template<typename Comparable>
void insertionSort(vector<Comparable> &a, int left, int right) {
    int i, j, tmp;
    for (i = left; i < right; i++) {
        if (a[i] < a[i - 1]) {
            tmp = a[i];
            for (j = i - 1; j >= 0 && a[j] > tmp; --j)
                a[j + 1] = a[j];
            a[j + 1] = tmp;
        }
    }
}

#endif //SORT_SORTING_H
